"""
给定一棵二叉搜索树（BST，左子树值 < 根值 < 右子树值），找出其中第 k 小的元素（k 从 1 开始计数）。
"""

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def kth_smallest(root, k):
    """寻找二叉搜索树的第k小元素（中序遍历特性：BST中序是升序）"""
    count = 0  # 记录已遍历的节点数
    result = None
    def inorder(node):
        nonlocal count, result
        if not node or result is not None:  # 找到结果后提前终止
            return
        inorder(node.left)  # 左子树（较小值）
        count += 1
        if count == k:  # 第k个节点，记录结果
            result = node.val
            return
        inorder(node.right)  # 右子树（较大值）
    inorder(root)
    return result

def create_binary_tree(arr):
    if not arr:
        return None
    root = TreeNode(arr[0])
    queue = [root]
    index = 1
    while queue and index < len(arr):
        current = queue.pop(0)
        if arr[index] is not None:
            current.left = TreeNode(arr[index])
            queue.append(current.left)
        index += 1
        if index < len(arr) and arr[index] is not None:
            current.right = TreeNode(arr[index])
            queue.append(current.right)
        index += 1
    return root

# 测试
# BST结构：
#       3
#      / \
#     1   4
#      \
#       2
root1 = create_binary_tree([3, 1, 4, None, 2])
print(kth_smallest(root1, 1))  # 输出: 1（第1小）
print(kth_smallest(root1, 3))  # 输出: 3（第3小）

# BST结构：
#        5
#       / \
#      3   6
#     / \
#    2   4
#   /
#  1
root2 = create_binary_tree([5, 3, 6, 2, 4, None, None, 1])
print(kth_smallest(root2, 3))  # 输出: 3（第3小）